#leetcode题目84：柱状图中最大的矩形
#难度：困难
#时间复杂度：O(n)
#空间复杂度：O(n)
#方法：栈,使用单调栈

from typing import List
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack=[0]
        res=0
        heights=[0]+heights+[0]
        for i in range(1,len(heights)):
            while heights[i]<heights[stack[-1]]:
                n=stack.pop()
                h=heights[n]
                w=i-stack[-1]-1

                res=max(res,h*w)
            stack.append(i)
        return res

#测试数据
heights=[2,1,5,6,2,3]
#预期输出：10
solution=Solution()
print(solution.largestRectangleArea(heights))

heights=[2,4]
#预期输出：4
solution=Solution()
print(solution.largestRectangleArea(heights))
